package codeTop;

public class lcr143 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        find(A,B);
        return res;
    }

    private void find(TreeNode a, TreeNode b) {
        if (res||a == null) {
            return;
        }
        if (a.val == b.val) {
            flag = true;
            dfs(a,b);
            res = flag;
        }
        find(a.left,b);
        find(a.right,b);
    }

    boolean flag = true;

    private void dfs(TreeNode a, TreeNode b) {
        if (!flag||b == null) {
            return;
        }
        if (a == null||a.val!=b.val) {
            flag = false;
            return;
        }
        dfs(a.left,b.left);
        dfs(a.right,b.right);
    }

    boolean res = false;

    public static void main(String[] args) {
        TreeNode treeA = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(4,
                                new TreeNode(8),
                                new TreeNode(9)
                        ),
                        new TreeNode(5)
                ),
                new TreeNode(3,
                        new TreeNode(6),
                        new TreeNode(7)
                )
        );
        TreeNode treeB = new TreeNode(4,
                new TreeNode(8),
                new TreeNode(9)
        );
        lcr143 q = new lcr143();
        q.isSubStructure(treeA,treeB);
    }
}
